package trees;

public class BinaryTree {

	static class Node {
		public Node(int v) {
			this.val = v;
		}

		int val;

		Node left, right;
	}

	/**
	 * Write a function to check if a binary tree is a binary search tree. 3
	 */
	public static void main(String[] args) {

		Node root = new Node(6);

		Node n1 = new Node(5);
		Node n2 = new Node(4);
		Node n3 = new Node(3);
		Node n4 = new Node(2);
		Node n5 = new Node(0);

		Node n6 = new Node(8);
		Node n7 = new Node(9);
		Node n8 = new Node(14);

		root.left = n3;
		root.right = n7;

		n7.right = n8;
		n7.left = n6;

		n3.left = n5;
		n5.right = n4;
		n3.right = n1;
		n3.left = n4;

		System.err.println(isValidBSTTree(root));

	}

	private static boolean isValidBSTTree(Node root) {

		return isValidBSTTree(root, null, null);
	}

	private static boolean isValidBSTTree(Node node, Integer min, Integer max) {

		if (node == null) {
			return true;
		} else {
			if ((min == null || node.val > min)
					&& (max == null || node.val < max)) {
				return isValidBSTTree(node.left, min, node.val)
						&& isValidBSTTree(node.right, node.val, max);
			} else {
				return false;
			}
		}
	}
}
